package com.wc.AlgoOJ_train.train2_DP训练.c3.DP0102;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/12 21:51
 * @description
 * 完全背包是从小到大
 */
public class Answer {
    static int maxN = 1000 + 7;
    static int[] ws = new int[maxN];
    static int[] vs = new int[maxN];
    static int[] dp = new int[maxN];
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            ws[i] = sc.nextInt();
            vs[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = ws[i]; j <= m; j++) {
                dp[j] = Math.max(dp[j], dp[j - ws[i]] + vs[i]);
            }
        }
        System.out.println(dp[m]);
    }
}
